home *** CD-ROM | disk | FTP | other *** search
/ PC PowerPlay 22 / PCPP #22.iso / Quake2 / q2source_12_11 / utils3 / bsp / qbsp3 / tree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-11-14  |  3.7 KB  |  199 lines
  1. #include "qbsp.h"
  2.  
  3. extern    int    c_nodes;
  4.  
  5. void RemovePortalFromNode (portal_t *portal, node_t *l);
  6.  
  7. node_t *NodeForPoint (node_t *node, vec3_t origin)
  8. {
  9.     plane_t    *plane;
  10.     vec_t    d;
  11.  
  12.     while (node->planenum != PLANENUM_LEAF)
  13.     {
  14.         plane = &mapplanes[node->planenum];
  15.         d = DotProduct (origin, plane->normal) - plane->dist;
  16.         if (d >= 0)
  17.             node = node->children[0];
  18.         else
  19.             node = node->children[1];
  20.     }
  21.  
  22.     return node;
  23. }
  24.  
  25.  
  26.  
  27. /*
  28. =============
  29. FreeTreePortals_r
  30. =============
  31. */
  32. void FreeTreePortals_r (node_t *node)
  33. {
  34.     portal_t    *p, *nextp;
  35.     int            s;
  36.  
  37.     // free children
  38.     if (node->planenum != PLANENUM_LEAF)
  39.     {
  40.         FreeTreePortals_r (node->children[0]);
  41.         FreeTreePortals_r (node->children[1]);
  42.     }
  43.  
  44.     // free portals
  45.     for (p=node->portals ; p ; p=nextp)
  46.     {
  47.         s = (p->nodes[1] == node);
  48.         nextp = p->next[s];
  49.  
  50.         RemovePortalFromNode (p, p->nodes[!s]);
  51.         FreePortal (p);
  52.     }
  53.     node->portals = NULL;
  54. }
  55.  
  56. /*
  57. =============
  58. FreeTree_r
  59. =============
  60. */
  61. void FreeTree_r (node_t *node)
  62. {
  63.     face_t        *f, *nextf;
  64.  
  65.     // free children
  66.     if (node->planenum != PLANENUM_LEAF)
  67.     {
  68.         FreeTree_r (node->children[0]);
  69.         FreeTree_r (node->children[1]);
  70.     }
  71.  
  72.     // free bspbrushes
  73.     FreeBrushList (node->brushlist);
  74.  
  75.     // free faces
  76.     for (f=node->faces ; f ; f=nextf)
  77.     {
  78.         nextf = f->next;
  79.         FreeFace (f);
  80.     }
  81.  
  82.     // free the node
  83.     if (node->volume)
  84.         FreeBrush (node->volume);
  85.  
  86.     if (numthreads == 1)
  87.         c_nodes--;
  88.     free (node);
  89. }
  90.  
  91.  
  92. /*
  93. =============
  94. FreeTree
  95. =============
  96. */
  97. void FreeTree (tree_t *tree)
  98. {
  99.     FreeTreePortals_r (tree->headnode);
  100.     FreeTree_r (tree->headnode);
  101.     free (tree);
  102. }
  103.  
  104. //===============================================================
  105.  
  106. void PrintTree_r (node_t *node, int depth)
  107. {
  108.     int        i;
  109.     plane_t    *plane;
  110.     bspbrush_t    *bb;
  111.  
  112.     for (i=0 ; i<depth ; i++)
  113.         printf ("  ");
  114.     if (node->planenum == PLANENUM_LEAF)
  115.     {
  116.         if (!node->brushlist)
  117.             printf ("NULL\n");
  118.         else
  119.         {
  120.             for (bb=node->brushlist ; bb ; bb=bb->next)
  121.                 printf ("%i ", bb->original->brushnum);
  122.             printf ("\n");
  123.         }
  124.         return;
  125.     }
  126.  
  127.     plane = &mapplanes[node->planenum];
  128.     printf ("#%i (%5.2f %5.2f %5.2f):%5.2f\n", node->planenum,
  129.         plane->normal[0], plane->normal[1], plane->normal[2],
  130.         plane->dist);
  131.     PrintTree_r (node->children[0], depth+1);
  132.     PrintTree_r (node->children[1], depth+1);
  133. }
  134.  
  135. /*
  136. =========================================================
  137.  
  138. NODES THAT DON'T SEPERATE DIFFERENT CONTENTS CAN BE PRUNED
  139.  
  140. =========================================================
  141. */
  142.  
  143. int    c_pruned;
  144.  
  145. /*
  146. ============
  147. PruneNodes_r
  148. ============
  149. */
  150. void PruneNodes_r (node_t *node)
  151. {
  152.     bspbrush_t        *b, *next;
  153.  
  154.     if (node->planenum == PLANENUM_LEAF)
  155.         return;
  156.     PruneNodes_r (node->children[0]);
  157.     PruneNodes_r (node->children[1]);
  158.  
  159.     if ( (node->children[0]->contents & CONTENTS_SOLID)
  160.     && (node->children[1]->contents & CONTENTS_SOLID) )
  161.     {
  162.         if (node->faces)
  163.             Error ("node->faces seperating CONTENTS_SOLID");
  164.         if (node->children[0]->faces || node->children[1]->faces)
  165.             Error ("!node->faces with children");
  166.  
  167.         // FIXME: free stuff
  168.         node->planenum = PLANENUM_LEAF;
  169.         node->contents = CONTENTS_SOLID;
  170.         node->detail_seperator = false;
  171.  
  172.         if (node->brushlist)
  173.             Error ("PruneNodes: node->brushlist");
  174.  
  175.         // combine brush lists
  176.         node->brushlist = node->children[1]->brushlist;
  177.  
  178.         for (b=node->children[0]->brushlist ; b ; b=next)
  179.         {
  180.             next = b->next;
  181.             b->next = node->brushlist;
  182.             node->brushlist = b;
  183.         }
  184.  
  185.         c_pruned++;
  186.     }
  187. }
  188.  
  189.  
  190. void PruneNodes (node_t *node)
  191. {
  192.     qprintf ("--- PruneNodes ---\n");
  193.     c_pruned = 0;
  194.     PruneNodes_r (node);
  195.     qprintf ("%5i pruned nodes\n", c_pruned);
  196. }
  197.  
  198. //===========================================================
  199.